Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.
This invention relates to the field of computer graphics, and more specifically, to rasterization using a tile-based digital differential analyzer algorithm.
Generally, the field of three-dimensional (3D) computer graphics is concerned with generating and displaying 3D objects in a two-dimensional (2D) space, such as a display screen. This is accomplished by converting information about 3D objects into a bit map that is displayed. This process is called rendering, a multi-part process by which a computer turns an application model description of an image into a screen image. The basic idea is that the processing of information in three-dimensional computer graphics occurs in a series of stages in a graphics pipeline, where each stage generates results for a successive stage.
The process starts with an application model for describing an object using three-dimensional coordinates (x, y, z), where the object is defined by large numbers of basic geometrical shapes called primitives that define the shape of components of the object. Examples of primitives that make up an object include a triangle, line, dot, circle, ellipse, arc, text, polyline, and polygon. In addition to primitives, an application model stores object attributes such as size, color, line, width, and surface texture, as well as connectivity relationships and positioning data that describe how the components fit together.
The application model for a given object is created by an application program, and stored in an application database. Using a graphics API (application programming interface), a series of graphics output commands that contain both a detailed geometric description of what is to be viewed and the attributes describing how the objects should appear, the application program converts the application model to a sequence of commands, which are then processed by a graphics pipeline to generate a view of the model. The graphics API typically consists of a set of output subroutines corresponding to the various primitives, attributes, and other elements, which are all collected in a graphics package that can be called from high-level languages such as C, Pascal, or LISP.
The basic element of any graphics system is rasterization, the process by which a primitive is converted to a two-dimensional image on a raster device. A raster device, such as a computer monitor, comprises a raster, the rectangular area of a display screen actually used to display images. A raster is itself made up of pixels, short for picture elements, the smallest units by which a primitive can be represented on a display. Pixels are activated on a raster device as an electron beam sweeps across the device to generate a picture one scan line at a time.
During rasterization, a primitive that is defined by 3D parameters in a three-dimensional (3D) representation is converted into a two-dimensional raster of pixels. 3D parameters comprise x, y, and z coordinates, and may optionally comprise parameters such as color, depth, and texture. During rasterization, each x and y parameter is converted into an x coordinate and a y coordinate. The 3D z coordinate, and any other parameters are then interpolated into 2D values.
One of the problems to be solved during the rasterization process is computing the 3D parameters, such as the Z coordinate, color, and texture, corresponding to the coordinates in order to most closely approximate the three-dimensional primitive. Rasterization, which is also known as scan conversion, makes these determinations by scanning the horizontal or vertical scan lines of the grid.
The rasterization process can be a costly and inefficient process, sometimes requiring many multiplication computations. While several algorithms exist, the process is commonly the subject of optimization algorithms.